package 二叉树;

import java.util.LinkedList;
import java.util.Queue;

public class _226_翻转二叉树 {
	public TreeNode invertTree1(TreeNode root) {
		if (root == null)
			return null;
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			TreeNode tmp = node.left;
			node.left = node.right;
			node.right = tmp;
			if (node.left != null) {
				queue.offer(node.left);
			}

			if (node.right != null) {
				queue.offer(node.right);
			}
		}
		return root;
	}

//	public TreeNode invertTree(TreeNode root) {
//		if (root == null)
//			return null;
//		TreeNode tmp = root.left;
//		root.left = root.right;
//		root.right = tmp;
//
//		invertTree(root.left);
//		invertTree(root.right);
//		return root;
//	}

	public TreeNode invertTree3(TreeNode root) {
		if (root == null)
			return null;
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);

		while (queue.size() > 0) {
			TreeNode node = queue.poll();
			TreeNode lefTreeNode = node.left;
			TreeNode righTreeNode = node.right;

			if (lefTreeNode != null) {
				queue.offer(lefTreeNode);
				node.right = lefTreeNode;
			} else {
				node.right = null;
			}

			if (righTreeNode != null) {
				queue.offer(righTreeNode);
				node.left = righTreeNode;
			} else {
				node.left = null;
			}
		}
		return root;
	}
}
